#ifndef __REFARRAY_H__
#define __REFARRAY_H__

#include <stdlib.h>
#include <string.h>
#include "Common.h"

namespace RayFrame
{
  template <typename T>
  class DLL_DECLARE RefCompareLess
  {
  public:
    static bool Compare(T t1, T t2)
    {
      return t1 < t2;
    }
  };

  /// simple fast array class
  template <class _Val, class _CompareFunc = RefCompareLess<_Val> >
  class DLL_DECLARE RefArray 
  {
  public:
    typedef _CompareFunc compare_t;
    typedef _Val val_t;

    RefArray()
    {
      m_count = m_capasity = 0;
      m_list = NULL;
    }

    RefArray(const unsigned int iCapasity)
    {
      m_count = 0;
      m_capasity = iCapasity;
      m_list = (val_t *) malloc(m_capasity * sizeof(val_t));
    }

    ~RefArray()
    {
      free(m_list);
    }

    val_t *GetArray() const { return m_list; }

    /// clear size counter and doesn't free the memory
    val_t *AbandonArray()
    {
      val_t *rList = m_list;
      m_list = NULL;
      return rList;
    }

    val_t &operator [] (const unsigned int index) const { return m_list[index]; }

    unsigned int GetCount() const { return m_count; }

    void SetCount(const unsigned int newCount)
    {
      m_capasity = m_count = newCount;
      m_list = (val_t *) realloc(m_list, m_capasity * sizeof(val_t));
    }

    unsigned int Add(const val_t object)
    {
      if (m_count >= m_capasity)
      {
        // resize to twice bigger
        if (m_capasity) m_capasity += m_capasity; else m_capasity = 8;
        m_list = (val_t *) realloc(m_list, m_capasity * sizeof(val_t));
      }
      m_list[m_count] = object;
      return m_count++;
    }

    void FastRemove(const unsigned int index)
    {
      if (index < m_count)
      {
        m_count--;
        m_list[index] = m_list[m_count];
      }
    }

    void OrderedRemove(const unsigned int index)
    {
      if (index < m_count)
      {
        m_count--;
        memmove(m_list + index, m_list + index + 1, (m_count - index) * sizeof(val_t));
      }
    }

    void clear()
    {
      m_count = 0;
    }

    /// delete the list and reset everything
    void reset()
    {
      free(m_list);
      m_list = NULL;
      m_count = m_capasity = 0;
    }

  private:
    int partition(int p, int r)
    {
      val_t tmp, pivot = m_list[p];
      int left = p;

      for (int i = p + 1; i <= r; i++)
      {
        if(compare_t::Compare(m_list[i], pivot) < 0)
        {
          left++;
          tmp = m_list[i];
          m_list[i] = m_list[left];
          m_list[left] = tmp;
        }
      }
      tmp = m_list[p];
      m_list[p] = m_list[left];
      m_list[left] = tmp;
      return left;
    }

    void quickSort(int p, int r)
    {
      if (p < r){
        int q = partition(p, r);
        quickSort(p, q - 1);
        quickSort(q + 1, r);
      }
    }
  public:
    void sort()
    {
      quickSort(0, m_count - 1);
    }
  protected:
    unsigned int m_capasity;
    unsigned int m_count;
    val_t *m_list;
  };

}

#endif // __REFARRAY_H__
